#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
class Solution
{
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() - 1;
        while (s[i] == s[j] && i < j)
        {
            i++, j--;
        }
        return (i == j) || (i - j == 1);
    }
    /**
     * 模式串: a b a b a b a
     * 匹配串: a b a b a b c
     * 
     * 
     * 逆s': d c b a
     * 串s :       a b c d
     * 
     * 逆s': a a a c e c a a
     * 串s :   a a c e c a a a
     * 只要求最长相等前后缀即可
     * 
     * 由于KMP算法中的next数组next[i]表示模式串T当第i个字符匹配失败,由T[1~i-1]组成的串为S
     * next[i] = S的最长相等前后缀长度+1
     */
    int get_next(int next[], string s)
    {
        int i = 1, j = 0;
        next[1] = 0;
        while (i < s.length())
        {
            if (j == 0 || s[i] == s[j])
            {
                ++i, ++j;
                next[i] = j;
            }
            else
            {
                j = next[j];
            }
        }
        return next[s.length()];
    }
    string shortestPalindrome(string s)
    {
        if (s.size() <= 1)
            return s;
        string sr = s;
        reverse(sr.begin(), sr.end());
        string T = s + "#" + sr;
        int *next = new int[T.length() + 1];
        int index = get_next(next, T);
        string suffix = s.substr(index, s.size());
        reverse(suffix.begin(), suffix.end());
        return suffix + s;
    }
};